import javax.swing.*;
import java.util.TreeMap;



 class Treemap {
    public static void main(String[] args) {
//        TreeMap<String,Integer> treeMap=new TreeMap();
//
//
//
//        treeMap.put("cha",12);
//
//        System.out.println(treeMap.get("cha"));
//
//        treeMap.comparator();

        insert(7);
        insert(4);
        insert(25);
        insert(5);

        insert(62);
        insert(26);
        insert(16);
        System.out.println(remove(62));

//        remove(25);
//        remove(16);








    }

    public static class Node {
        int key;
        Node left;
        Node right;
        public Node(int key) {
            this.key = key;
        }
    }

    static Node root=null;




    public static Node search(int key){
        Node cur= root;

        while (cur!=null){
            if(cur.key==key){

                return cur;

            }else if(key>cur.key){
                cur=cur.right;
            }else {
                cur=cur.left;
            }


        }


        return null;



    }

    public static boolean insert(int key){
        if(root==null){
            root=new Node(key);
            return true;
        }

        Node cur=root;
        Node parent=null;
        while (cur!=null){

            if(key>cur.key){
                parent=cur;
                cur=cur.right;
            }else if(key<cur.key){
                parent=cur;
                cur=cur.left;
            }else {
                return false;
            }


        }

        if(key> parent.key){
            parent.right=new Node(key);
        }else {
            parent.left=new Node(key);
        }

        return true;

    }


    public static boolean remove(int key) {


        Node cur = root;
        Node parent = null;


        while (cur != null) {
            if (key > cur.key) {
                parent = cur;
                cur = cur.right;

            } else if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else {
                break;
            }
        }


        if (cur == null) {
            return false;
        }


        if (cur.left == null && cur.right == null) {
            if (parent.right == cur) {
                parent.right = null;
            } else {
                parent.left = null;
            }

            return true;
        }

        if (cur.left == null) {
            if (parent.right == cur) {
                parent.right = cur.right;
            } else {
                parent.left = cur.right;
            }
            return true;
        }


        if (cur.right == null) {
            if (parent.right == cur) {
                parent.right = cur.left;
            } else {
                parent.left = cur.left;
            }
            return true;
        }


        //替换删除法
        Node target = cur.left;
        Node tParent = cur;


        while (target.right != null) {
            tParent = target;
            target = tParent.right;

        }


        if (parent.right == cur) {
            if (cur.left != target) {
                tParent.right = target.left;

                parent.right = target;
                target.left = cur.left;
                target.right = cur.right;

                return true;
            } else {
                parent.right = target;
                target.right = cur.right;
                target.left = null;
                return true;
            }
        } else {
            if (cur.left != target) {

                parent.left = target;
                target.left = cur.left;
                target.right = cur.right;
                return true;
            } else {
                parent.left = target;
                target.right = cur.right;
                target.left = null;
                return true;

            }

        }
    }




     public void remove1(int key) {
         Node cur = root;
        Node parent = null;
         while (cur != null) {
             if(cur.key < key) {
                 parent = cur;
                 cur = cur.right;
             }else if(cur.key > key) {
                 parent = cur;
                 cur = cur.left;
             }else {
                 removeNode(parent,cur);
                 return;
             }
         }
     }

     private void removeNode(Node parent, Node cur) {
         if(cur.left == null) {
             if(cur == root) {
                 root = cur.right;
             }else if(parent.left == cur) {
                 parent.left = cur.right;
             }else {
                 parent.right = cur.right;
             }
         }else if(cur.right == null) {
             if(cur == root) {
                 root = cur.left;
             }else if(parent.left == cur) {
                 parent.left = cur.left;
             }else {
                 parent.right = cur.left;
             }
         }else {
             Node targetParent = cur;
            Node target = cur.right;
             while (target.left != null) {
                 targetParent = target;
                 target = target.left;
             }
             cur.key = target.key;
             if(targetParent.left == target) {
                 targetParent.left = target.right;
             }else {
                 targetParent.right = target.right;
             }
         }
     }




}
